package com.hy.treeNode2;

import com.hy.treeNode.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreePaths {

    /**
     * 257. 二叉树的所有路径
     * 力扣题目链接
     *
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 思路
     * 这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
     *
     * 在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一一个路径在进入另一个路径。
     *
     * 前序遍历以及回溯的过程如图：
     *
     * 递归
     * 1.递归函数函数参数以及返回值
     * 要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：
     *
     * void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)
     * 2.确定递归终止条件
     * 再写递归的时候都习惯了这么写：
     *
     * if (cur == NULL) {
     *     终止处理逻辑
     * }
     *
     * 3.确定单层递归逻辑
     * 因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。
     *
     * path.push_back(cur->val);
     *
     * 然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。
     *
     * 总结
     * 本文我们开始初步涉及到了回溯，很多同学过了这道题目，可能都不知道自己其实使用了回溯，回溯和递归都是相伴相生的。
     *
     * 我在第一版递归代码中，把递归与回溯的细节都充分的展现了出来，大家可以自己感受一下。
     *
     * 第二版递归代码对于初学者其实非常不友好，代码看上去简单，但是隐藏细节于无形。
     *
     * 最后我依然给出了迭代法。
     *
     * 对于本地充分了解递归与回溯的过程之后，有精力的同学可以在去实现迭代法。
     * @param root
     * @return
     */
    // 迭代法
    public List<String> binaryTreePaths2(TreeNode root){
        List<String> res = new ArrayList<>();
        Stack<Object> st = new Stack<>();
        if (root == null){
            return res;
        }
        // 节点和路径同时入栈
        st.push(root);
        st.push(root.val +"");
        while (!st.isEmpty()){
            String  path = (String) st.pop();
            TreeNode node = (TreeNode) st.pop();
            if (node.left == null && node.right == null){
                res.add(path);
            }
            //右子节点不为空
            if (node.right != null){
                st.push(node.right);
                st.push(path +"->"+node.right.val);
            }
            // 左子节点不为空
            if (node.left != null){
                st.push(node.left);
                st.push(path +"->"+node.left.val);
            }
        }
        return res;
    }
    // 递归
    public List<String> binaryTreePaths(TreeNode root){
        List<String> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        List<Integer> paths = new ArrayList<>();
        traversal(root,paths,res);
        return res;
    }


    public void traversal(TreeNode root, List<Integer> paths,List<String> res){
        paths.add(root.val);
        // 叶子节点
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            // 输出
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            // 截取
            sb.append(paths.get(paths.size() -1));
            res.add(sb.toString());
            return;
        }

        if (root.left != null){
            traversal(root.left,paths,res);
            // 回溯  5 -> 4 -> 1      5 -> 4 ->
            paths.remove(paths.size() - 1);
        }
        if (root.right != null){
            traversal(root.right,paths,res);
            // 回溯  5 -> 4 -> 2      5 -> 4 ->
            paths.remove(paths.size() - 1);
        }
    }

    public static void main(String[] args) {

        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        BinaryTreePaths binaryTreePaths = new BinaryTreePaths();
        System.out.println("res: "+binaryTreePaths.binaryTreePaths(root));
        System.out.println("res: "+binaryTreePaths.binaryTreePaths2(root));

    }
}
